package com.ithemima.peek;

import java.util.HashSet;
import java.util.Set;
// 定义链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }
    public static void main(String[] args) {
// 创建一个有环的链表用于测试
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // 创建环

        Solution solution = new Solution();
        ListNode cycleStart = solution.detectCycle(node1);
        if (cycleStart != null) {
            System.out.println("环的起始节点值为: " + cycleStart.val);
        } else {
            System.out.println("链表中不存在环");
        }

    }
}
